//
// Created by 123 on 2024/4/1.
//
/**
 *  折半插入排序
 *      默认前面有序，诸逐个拿后面的无序序列和
 *  前面的有序数列，然后决定插入位置
 *
 *  加速 ：在查找有序数列的插入位置时，用折半查找的
 *  方式，折半查找后，插入的位置为 low+1
 *
 *   O（n^2)
 */
#include <iostream>

using namespace std;

#define MaxSize 100

typedef struct Array {
    int data[MaxSize];
    int length;
} Array, *Arr;

Array *initArray(int arr[], int len);

void swap(int &a, int &b);


void half_inser_sort(Arr &arr);


int main() {
    int a[10]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    Arr arr = initArray(a, 10);
    half_inser_sort(arr);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
}

void half_inser_sort(Arr &arr) {
//    下标从 1 开始，默认0有序
    for (int i = 1; i < arr->length; ++i) {
        if (arr->data[i] < arr->data[i - 1]) {
            int data = arr->data[i];
            int min = 0;
            int max = i - 1;
            while (min <= max) {
                int mid = (max + min) / 2;
//                为保证排序的稳定性，所有要保证等于时，后面的依旧在后面
//                即等于时，min需要在mid的基础上右移
                if (data >= arr->data[mid])
                    min = mid + 1;
                else if (data < arr->data[mid])
                    max = mid - 1;
            }
            int j=i;
            for ( j ; j >max+1; j--) {
                arr->data[j]=arr->data[j-1];
            }
            arr->data[j]=data;
        }

    }
}


Array *initArray(int arr[], int len) {
    Arr array = (Array *) malloc(sizeof(Array));
    for (int i = 0; i < len; ++i) {
        array->data[i] = arr[i];
    }
    array->length = len;
    return array;
}

void swap(int &a, int &b) {
    int turn = a;
    a = b;
    b = turn;
}